package everyday;

import java.util.Arrays;

/**
 * @author ZhanBo
 * @date 2020/6/4
 */
public class Solution238 {

    public static void main(String[] args) {
        int [] array ={1,2,3,4};
        System.out.println(Arrays.toString(productExceptSelf(array)));
    }


    /**
     *238. 除自身以外数组的乘积
     *
     *
     *给你一个长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。
     输入: [1,2,3,4]
     输出: [24,12,8,6]
     提示：题目数据保证数组之中任意元素的全部前缀元素和后缀（甚至是整个数组）的乘积都在 32 位整数范围内。
     说明: 请不要使用除法，且在 O(n) 时间复杂度内完成此题。
     * @param nums
     * @return
     */
    public static int[] productExceptSelf(int[] nums) {
        int[] result = new int[nums.length];
        int k = 1;
        for(int i = 0; i < result.length; i++){
            // 此时数组存储的是除去当前元素左边的元素乘积
            result[i] = k;
            // k为该数左边的乘积。
            k = k * nums[i];
        }
        k = 1;
        for(int i = result.length - 1; i >= 0; i--){
            // 此时数组等于左边的 * 该数右边的。
            result[i] = result[i] * k;
            // k为该数右边的乘积。
            k = k * nums[i];
        }
        return result;
    }
}
